#include <bits/stdc++.h>

using namespace std;

const int N=1e5+10,INF=2147483647;

int n,m,s;
vector<pair<int,int>> mp[N];
int dist[N];
bool st[N];

void spfa()
{
	for(int i=1;i<=n;i++) dist[i]=INF;
	dist[s]=0;
	queue<int> q;
	q.push(s);
	st[s]=true;
	while(q.size())
	{
		int u=q.front(); q.pop();
		st[u]=false;
		
		for(auto& e:mp[u])
		{
			int v=e.first,w=e.second;
			if(dist[u]+w<dist[v])
			{
				dist[v]=dist[u]+w;
				if(!st[v]) 
				{
					q.push(v);
					st[v]=true; 
				}
			}
		}
	}
	for(int i=1;i<=n;i++) cout<<dist[i]<<" ";
}

int main() 
{
	cin>>n>>m>>s;
	for(int i=1;i<=m;i++)
	{
		int u,v,w;cin>>u>>v>>w;
		mp[u].push_back({v,w});
	}
	
	spfa();
	
	return 0;
}
